#include <stdio.h>
#include <stdlib.h>
#define N 100
typedef char datatype;
typedef struct node 	/*śţ˛ćĘ÷˝áššś¨Ňĺ*/
{
    datatype data;
    struct node *lch,*rch;
}bnode;

bnode *creat()
{
    bnode *p;
    char c;
    scanf("%c", &c);
    if(c=='#') return p=NULL;
    p=(bnode *)malloc(sizeof(bnode));
    p->data=c;
    p->lch=creat();
    p->rch=creat();
    return p;
}


void fstorder(bnode *p)  	/*ĎČĐňľÝšéąéŔúśţ˛ćĘ÷*/
{
    if(p)
    {
        printf("%c",p->data);
        fstorder(p->lch);
        fstorder(p->rch);
    }
}
void lastorder(bnode *p) 	/*şóĐňľÝšéąéŔúśţ˛ćĘ÷*/
{
    if(p)
    {
        lastorder(p->lch);
        lastorder(p->rch);
        printf("%c",p->data);
    }
}

/*ËłĐňŐťś¨Ňĺ*/
typedef struct
{
    bnode *data[N];
    int top;
}sqstack;

void init(sqstack *s)   /*łőĘźťŻżŐŐť*/
{
    s->top=-1;
}
int empty(sqstack *s)   /*ĹĐśĎŐťĘÇˇńÎŞżŐ*/
{
    if(s->top>-1) return 0;
    else return 1;
}
int full(sqstack *s)    /*ĹĐśĎŐťĘÇˇńÎŞÂú*/
{
    if(s->top==N-1) return 1;
    else return 0;
}
void push(sqstack *s ,bnode *x)  /*˝řŐť*/
{
    if(!full(s))
        s->data[++s->top]=x;
}
bnode *pop(sqstack *s)			/*łöŐť*/
{
    if(!empty(s))
        return s->data[s->top--];
}
